#include <array>
#include <iostream>
#include<string>
class tri {
public:
    const static int MAX_SIZE = 150001;
    std::array<std::array<int, 26>, MAX_SIZE> tree{}; // 自动初始化为0
    std::array<int, MAX_SIZE> end{};
    std::array<int, MAX_SIZE> p{};
    int cnt = 1;

    tri() = default; // 默认构造函数已足够
    ~tri() = default;

    void insert(const std::string& word)
    {
        int index = 1;
        p[1]++;
        for (const char& c :word)
        {
            int now = c - 'a';
            if (tree[index][now] == 0)
            {
                tree[index][now] = ++cnt;
              
            }
            index = tree[index][now];
            p[index]++;
        }
        end[index]++;

    }
    void del(const std::string& word)
    {
        if (!search(word)) return;
        int index = 1;
        p[1]--;
        for (const char& c :word)
        {
            int now = c - 'a';
            if (--p[tree[index][now]] == 0)
            {
                tree[index][now] = 0;
                return;
            }
      index = tree[index][now];
    
        }
        end[index]--;
   
    }
    bool search(const std::string& word)
    {
        int index = 1;
        for (const char& c : word)
        {
            int now = c - 'a';
            if (tree[index][now] == 0)
            {
                return false;
            }
            index = tree[index][now];
        }
        if (end[index] == 0) return false;
        return true;
    }
    int s(const std::string& word)
    {
        int index = 1;
       
        for (const char& c : word)
        {
            int now = c - 'a';
            index = tree[index][now];
        }
        return p[index];
    }
};
